<?php
namespace helper\calc;
/**
 * 执行字符串运算
 * Parser::parse($trm);
 * //高级执行字符串运算
 * $ctx = new Context;
 * ctx->def('abs'); // wrapper
 * $ctx->def('foo', 5);
 * $ctx->def('bar', function($a, $b) { return $a * $b; });
 * $trm = '3 + bar(4, 2) / (abs(-1) - foo) ^ 2 ^ 3';
 * print Parser::parse($trm, $ctx); // 3.0001220703125
 *
 * Class Parser
 * @package helper\calc
 */
class Parser
{
  const ST_1 = 1, // wartet auf operand oder unäre vorzeichen
      ST_2 = 2; // wartet auf operator

  protected $scanner, $state = self::ST_1;
  protected $queue, $stack;

  public function __construct(Scanner $scanner)
  {
    $this->scanner = $scanner;

    // alloc
    $this->queue = array();
    $this->stack = array();

    // queue erzeugen
    while (($t = $this->scanner->next()) !== false)
      $this->handle($t);

    // When there are no more tokens to read:
    // While there are still operator tokens in the stack:
    while ($t = array_pop($this->stack)) {
      if ($t->type === 8 || $t->type === 16)
        throw new \Exception('解析器错误:\'（\'和\'）\'的嵌套不正确');

      $this->queue[] = $t;
    }
  }

  public function reduce(Context $ctx)
  {
    $this->stack = array();
    $len         = 0;

    // While there are input tokens left
    // Read the next token from input.
    while ($t = array_shift($this->queue)) {
      switch ($t->type) {
        case 1:
        case 2:
          // wert einer konstanten ermitteln
          if ($t->type === 2)
            $t = new Token(1, $ctx->cs($t->value));

          // If the token is a value or identifier
          // Push it onto the stack.
          $this->stack[] = $t;
          ++$len;
          break;

        case 65:
        case 66:
        case 71:
        case 72:
        case 67:
        case 68:
        case 69:
        case 70:
        case 73:
          // It is known a priori that the operator takes n arguments.
          $na = $this->argc($t);

          // If there are fewer than n values on the stack
          if ($len < $na)
            throw new \Exception('操作参数太少:' . $t->value . '" (' . $na . ' -> ' . $len . ')');

          $rhs = array_pop($this->stack);
          $lhs = null;

          if ($na > 1)
            $lhs = array_pop($this->stack);

          // if ($lhs) print "{$lhs->value} {$t->value} {$rhs->value}\n";
          // else print "{$t->value} {$rhs->value}\n";

          $len -= $na - 1;

          // Push the returned results, if any, back onto the stack.
          $this->stack[] = new Token(1, $this->op($t->type, $lhs, $rhs));
          break;

        case 4:
          // function
          $argc = $t->argc;
          $argv = array();

          $len -= $argc - 1;

          for (; $argc > 0; --$argc)
            array_unshift($argv, array_pop($this->stack)->value);

          // Push the returned results, if any, back onto the stack.
          $this->stack[] = new Token(1, $ctx->fn($t->value, $argv));
          break;

        default:
          throw new \Exception('令牌错误:' . $t->value . '`');
      }
    }

    // If there is only one value in the stack
    // That value is the result of the calculation.
    if (count($this->stack) === 1)
      return array_pop($this->stack)->value;

    // If there are more values in the stack
    // (Error) The user input has too many values.
    throw new \Exception('堆栈中的值太多');
  }

  protected function op($op, $lhs, $rhs)
  {
    if ($lhs !== null) {
      $lhs = $lhs->value;
      $rhs = $rhs->value;

      switch ($op) {
        case 65:
          return $lhs + $rhs;

        case 66:
          return $lhs - $rhs;

        case 67:
          return $lhs * $rhs;

        case 68:
          if ($rhs === 0.)
            throw new \Exception('除数不能为0');

          return $lhs / $rhs;

        case 69:
          if ($rhs === 0.)
            throw new \Exception('除数不能为0');

          // php (bzw. c) kann hier nur mit ganzzahlen umgehen
          return (float)$lhs % $rhs;

        case 70:
          return (float)pow($lhs, $rhs);
      }
    }

    switch ($op) {
      case 73:
        return (float)!$rhs->value;

      case 72:
        return -$rhs->value;

      case 71:
        return +$rhs->value;
    }
    return 0;
  }

  protected function argc(Token $t)
  {
    switch ($t->type) {
      case 65:
      case 66:
      case 67:
      case 68:
      case 69:
      case 70:
        return 2;
    }

    return 1;
  }

  public function dump($str = false)
  {
    if ($str === false) {
      print_r($this->queue);
      return;
    }

    $res = array();

    foreach ($this->queue as $t) {
      $val = $t->value;

      switch ($t->type) {
        case 72:
        case 71:
          $val = 'unary' . $val;
          break;
      }

      $res[] = $val;
    }

    print implode(' ', $res);
  }

  protected function fargs($fn)
  {
    $this->handle($this->scanner->next()); // '('

    $argc = 0;
    $next = $this->scanner->peek();

    if ($next && $next->type !== 16) {
      $argc = 1;

      while ($t = $this->scanner->next()) {
        $this->handle($t);

        if ($t->type === 16)
          break;

        if ($t->type === 32)
          ++$argc;
      }
    }

    $fn->argc = $argc;
  }

  protected function handle(Token $t)
  {
    switch ($t->type) {
      case 1:
      case 2:
        // If the token is a number (identifier), then add it to the output queue.
        $this->queue[] = $t;
        $this->state   = self::ST_2;
        break;

      case 4:
        // If the token is a function token, then push it onto the stack.
        $this->stack[] = $t;
        $this->fargs($t);
        break;


      case 32:
        // If the token is a function argument separator (e.g., a comma):

        $pe = false;

        while ($t = end($this->stack)) {
          if ($t->type === 8) {
            $pe = true;
            break;
          }

          // Until the token at the top of the stack is a left parenthesis,
          // pop operators off the stack onto the output queue.
          $this->queue[] = array_pop($this->stack);
        }

        // If no left parentheses are encountered, either the separator was misplaced
        // or parentheses were mismatched.
        if ($pe !== true)
          throw new \Exception('解析器错误"("');

        break;

      // If the token is an operator, op1, then:
      case 65:
      case 66:
      case 71:
      case 72:
      case 67:
      case 68:
      case 69:
      case 70:
      case 73:
        while (!empty($this->stack)) {
          $s = end($this->stack);

          // While there is an operator token, o2, at the top of the stack
          // op1 is left-associative and its precedence is less than or equal to that of op2,
          // or op1 has precedence less than that of op2,
          // Let + and ^ be right associative.
          // Correct transformation from 1^2+3 is 12^3+
          // The differing operator priority decides pop / push
          // If 2 operators have equal priority then associativity decides.
          switch ($s->type) {
            default:
              break 2;

            case 65:
            case 66:
            case 71:
            case 72:
            case 67:
            case 68:
            case 69:
            case 70:
            case 73:
              $p1 = $this->preced($t);
              $p2 = $this->preced($s);

              if (!(($this->assoc($t) === 1 && ($p1 <= $p2)) || ($p1 < $p2)))
                break 2;

              // Pop o2 off the stack, onto the output queue;
              $this->queue[] = array_pop($this->stack);
          }
        }

        // push op1 onto the stack.
        $this->stack[] = $t;
        $this->state   = self::ST_1;
        break;

      case 8:
        // If the token is a left parenthesis, then push it onto the stack.
        $this->stack[] = $t;
        $this->state   = self::ST_1;
        break;

      // If the token is a right parenthesis:
      case 16:
        $pe = false;

        // Until the token at the top of the stack is a left parenthesis,
        // pop operators off the stack onto the output queue
        while ($t = array_pop($this->stack)) {
          if ($t->type === 8) {
            // Pop the left parenthesis from the stack, but not onto the output queue.
            $pe = true;
            break;
          }

          $this->queue[] = $t;
        }

        // If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
        if ($pe !== true)
          throw new \Exception('解析器错误")"');

        // If the token at the top of the stack is a function token, pop it onto the output queue.
        if (($t = end($this->stack)) && $t->type === T_FUNCTION)
          $this->queue[] = array_pop($this->stack);

        $this->state = self::ST_2;
        break;

      default:
        throw new \Exception('解析器错误：未知令牌:' . $t->value);
    }
  }

  protected function assoc(Token $t)
  {
    switch ($t->type) {
      case 67:
      case 68:
      case 69:

      case 65:
      case 66:
        return 1; //ltr

      case 73:
      case 71:
      case 72:

      case 70:
        return 2; //rtl
    }

    // ggf. erweitern :-)
    return 0; //nassoc
  }

  protected function preced(Token $t)
  {
    switch ($t->type) {
      case 71:
      case 72:
      case 73:
        return 4;

      case 70:
        return 3;

      case 67:
      case 68:
      case 69:
        return 2;

      case 65:
      case 66:
        return 1;
    }

    return 0;
  }

  public static function parse($term, Context $ctx = null)
  {
    $scanner = new Scanner($term);
    $obj = new Parser($scanner);
    return $obj->reduce($ctx ?: new Context);
  }
}